package com.mokairui.linear;

/**
 * @Description 栈 - 括号匹配问题
 * @Author Mokairui
 * @Since 2022/3/26
 */
public class BracketsMatch {
    public static void main(String[] args) {
        String str = "(上海(长安)())";
        boolean match = isMatch(str);
        System.out.println(str + "中的括号是否匹配:" + match);
    }

    /**
     * 判断str中的括号是否匹配
     * @param str 括号组成的字符串
     * @return 如果匹配, 返回true, 如果不匹配返回false
     */
    public static boolean isMatch(String str) {
        // 1.创建栈对象,用来存储左括号
        Stack<String> stack = new Stack<>();
        // 2.从左往右遍历字符串
        for (int i = 0; i < str.length(); i++) {
            String strIndex = String.valueOf(str.charAt(i));
            // 3.判断当前字符串是否为左括号,如果是则把字符串放入栈中
            if (strIndex.equals("(")) {
                stack.push(strIndex);
            } else if (strIndex.equals(")")) {
                // 4.当前字符是否是右括号,如果是则从栈中弹出一个左括号, 如果弹出结果是null, 证明没有匹配左括号, 如果有则匹配一个左括号成功
                String rightBracket = stack.pop();
                if (rightBracket == null) {
                    return false;
                }
            }
        }
        // 5.判断栈中是否还有左括号, 如果有, 则证明括号不匹配
        if (stack.isEmpty()) {
            return true;
        }
        return false;
    }
}
